package com.hy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2192. 有向无环图中一个节点的所有祖先
 * <p>
 * 给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。
 * 给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。
 * 请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。
 * 如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。
 * <p>
 * User:Mr.Du
 * Date:2024/5/6
 * Time:18:40
 */
public class GetAncestors {

    List<Integer> l = new ArrayList<>();
    public List<List<Integer>> getAncestors1(int n, int[][] edges) {
        List<Integer>[] list = new List[n];
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.setAll(list, e -> new ArrayList<>());
        for(int[] edge : edges){
            int x = edge[0], y = edge[1];
            list[y].add(x);
        }
        for(int i = 0;i < n;i++){
            int y = i;
            dfs1(i, list);
            Collections.sort(l, (a, b) -> a - b);
            ans.add(new ArrayList<>(l));
            l.clear();
        }
        return ans;
    }


    public void dfs1(int i, List<Integer>[] r){
        if(r[i] == null) return;
        for(int x : r[i]){
            if(l.contains(x)) continue;
            l.add(x);
            dfs1(x, r);
        }
    }

    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[1]].add(e[0]); // 反向建图
        }

        List<Integer>[] ans = new ArrayList[n];
        Arrays.setAll(ans, i -> new ArrayList<>());
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(vis, false);
            dfs(i, g, vis); // 从 i 开始 DFS
            vis[i] = false; // ans[i] 不含 i
            for (int j = 0; j < n; j++) {
                if (vis[j]) {
                    ans[i].add(j);
                }
            }
        }
        return Arrays.asList(ans);
    }

    private void dfs(int x, List<Integer>[] g, boolean[] vis) {
        vis[x] = true; // 避免重复访问
        for (int y : g[x]) {
            if (!vis[y]) {
                dfs(y, g, vis); // 只递归没有访问过的点
            }
        }
    }
}
